package com.mgq.algorithm.twotree;

import java.util.List;

/**
 * 派对的最大快乐值
 * 员工信息的定义如下:
 * class Employee {
 * public int happy;//这名员工可以带来的快乐值
 * List<Employee> subordinates; //这名员工有哪些直接下级
 * }
 * 公司的每个员工都符合Employee类的描述。整个公司的人员结构可以看作是一棵标准的、没有环的多叉树。树的头节点是公司唯一的老板。
 * 除老板之外的每个员工都有唯一的直接上级。叶节点是没有任何下属的基层员工(subordinates列表为空)，
 * 除基层员工外，每个员工都有一个或多个直接下级。这个公司现在要办party，你可以决定哪些员工来，哪些员工不来。但是要遵循如下规则。
 * 1.如果某个员工来了，那么这个员工的所有直接下级都不能来
 * 2.派对的整体快乐值是所有到场员工快乐值的累加
 * 3.你的目标是让派对的整体快乐值尽量大
 * 给定一棵多叉树的头节点boss，请返回派对的最大快乐值。
 */
public class PartySolution {
    public static int partMaxHappy(Employee boss) {
        Info maxInfo = process(boss);
        return Math.max(maxInfo.bulaiMaxHappy, maxInfo.laiMaxHappy);
    }
    public static Info process(Employee employee){
        /**
         * 分析情况
         *                 X
         *             /  |   \
         *            a   b    c
         *           /\\
         * 情况1. X参与
         * 直接下级不能来
         * 整体的快乐值就是 X快乐值+a不来的整体快乐值+b不来的整体快乐值+c不来的整体快乐值
         * 情况2. X不参与
         *  a可以选择参与或者不参与
         *  整体的快乐值就是 0(x不参与)+[a来|a不来 (最最大值)]+[b来|b不来 (最最大值)]+[c来|c不来 (最最大值)]
         *
         *  结构信息就是 来最大快乐值 不来最大快乐值
         */
        //说明是最基层员工 base case
        if (employee.subordinates.isEmpty()) {
            return new Info(0, employee.happy);
        }
        int lai = employee.happy;
        int bu=0;
        for (Employee next : employee.subordinates) {
            Info info = process(next);
            // x参与的情况
            lai +=info.bulaiMaxHappy;
            //x不来的情况
            bu += Math.max(info.bulaiMaxHappy, info.laiMaxHappy);
        }
        return new Info(bu, lai);
    }

    public static class Info {
        private int bulaiMaxHappy;
        private int laiMaxHappy;

        public Info(int bulaiMaxHappy, int laiMaxHappy) {
            this.bulaiMaxHappy = bulaiMaxHappy;
            this.laiMaxHappy = laiMaxHappy;
        }
    }
    public static class Employee{
        /**
         * 这名员工可以带来的快乐值
         */
        private int happy;
        /**
         * 这名员工有哪些直接下级
         */
        private List<Employee> subordinates;
    }
}


